Cache is used to reduce average access time of data elements for processing. Cache is typically organized into cache sets, where each cache set includes multiple cache blocks. Each cache block contains multiple data elements. Because a cache contains a subset of data elements in main memory, the cache can be made smaller than the main memory and allows faster access than the main memory. Data elements that are not contained in the cache need to be retrieved from the main memory. Retrieving new data elements from the main memory into the cache typically requires replacing existing data elements in cache blocks.
Least recently used (LRU) cache replacement schemes, which are based on the assumption that data elements in the LRU cache block of a cache set will be the least likely to be used in the near future and are therefore the best candidates for replacement in the cache set, provide an order of time in terms of usage of cache blocks in a cache set. Full LRU cache replacement schemes provide a perfect order in time in terms of usage of cache blocks in a cache set. However, implementations of full LRU cache replacement schemes require a large amount of bits for representing the perfect order in time. Hierarchical LRU cache replacement schemes are introduced to provide a near perfect order in time in terms of usage of cache blocks in a cache set. Compared to the implementations of full LRU cache replacement schemes, implementations of hierarchical LRU cache replacement schemes require fewer bits for representing the near perfect order.
A concern with such hierarchical LRU cache replacement schemes is the imperfect order in time. Because of the imperfect order in time, a cache block that is not the LRU cache block in a cache set may be mistakenly identified as the LRU cache block in the cache set. As a result, the performance of hierarchical LRU cache replacement schemes is impacted.
BRIEF SUMMARY OF THE INVENTION
A system and method for replacing data in a cache utilizes cache block validity information to maintain least recently used information of cache blocks in a cache set of the cache, identifies the least recently used cache block of the cache set using the least recently used information of the cache blocks in the cache set, and replaces data in the least recently used cache block of the cache set with data from main memory.
In an embodiment, a method for replacing data in a cache includes maintaining least recently used information of cache blocks in a cache set of the cache using cache block validity information, identifying the least recently used cache block of the cache set using the least recently used information of the cache blocks in the cache set and replacing data in the least recently used cache block of the cache set with data from main memory.
In an embodiment, a video processing system includes main memory, a cache, a video processor and a cache management unit. The main memory is configured to store a data working set. The cache is coupled to the main memory and configured to cache a subset of the data working set. The video processor is coupled to the cache and configured to process the subset of the data working set. The cache management unit is configured to maintain least recently used information of cache blocks in a cache set of the cache using cache block validity information, identify the least recently used cache block of the cache set using the least recently used information of the cache blocks in the cache set, and replace data in the least recently used cache block of the cache set with data from the data working set stored at the main memory.
In an embodiment, a method for replacing data in a cache in a video processing system includes dividing cache blocks in a cache set of the cache in the video processing system into cache block groups, where each of the cache block groups includes multiple cache blocks, maintaining least recently used information of the cache blocks in the cache set using cache block validity information, identifying the least recently used cache block of the cache set using the least recently used information of the cache blocks in the cache set and replacing data in the least recently used cache block of the cache set with data from main memory in the video processing system.